package algo.A02_查找排序基础;

import util.ArrayUtil;

/**
 * 插入排序
 */
public class M04_InsertSort {
    public static void main(String[] args) {
        int[] randomArr = ArrayUtil.getRandomArr(10, 0, 100);
        ArrayUtil.print(randomArr);
        insertSort(randomArr);
        ArrayUtil.print(randomArr);
    }

    public static void insertSort(int[] arr){
        //类似于摸牌，从上到下一张一张去摸
        for (int i = 0; i < arr.length; i++) {
            //摸到的这张牌是arr[i],手上的牌有arr[0]~arr[i-1]
            //原有手牌最后一张的位置
            int lastIndex = i - 1;
            //新摸到的手牌
            int now = arr[i];
            //只要新摸到的牌比最后一张小，就把最后一张往后面移动
            while (lastIndex >= 0 && now < arr[lastIndex]){
                arr[lastIndex + 1] = arr[lastIndex];
                lastIndex--;//每移动一次，最后一张牌的位置要向前移动一个
            }
            //退出循环:lastIndex==0或新手牌更大了
            //把新手牌放在最后一张牌的后面
            arr[lastIndex + 1] = now;
        }
    }
}
